// 希尔排序

#include <iostream>
#include <algorithm>

// 缩小增量进行排序 
void shellSort(int arr[], int n)
{
    int i, j, increment, tmp;
    for (increment = n / 2; increment > 0; increment /= 2) // 当增量为0排序完成(怎么体现 ? 增量为1时就相当于插入排序可直接排序完成)
    {
        for (i = increment; i < n; ++i)
        {
            tmp = arr[i];
            for (j = i - increment; j >= 0 && arr[j] > tmp; j -= increment)
            {
                arr[j + increment] = arr[j];
            }
            arr[j + increment] = tmp;
        }
    }
}
